1. Field of the Invention
The present invention relates to protection of random number generation in embedded circuitry, and more specifically, to the protection of random number generation on embedded micro-control circuits.
2. Description of the Related Art
High quality random number generators are important features, among other things, for embedded chips that provide cryptographic operations in the marketplace. The quality of outputs from such random numbers generators is particularly critical. The Random Number Generator (RNG) may be used to provide input for cryptographic algorithms. This is the basis for how these mathematically secure operations can be achieved. These cryptographic operations can include Data Encryption Standard (DES) also known as (symmetric), the RSA algorithm (invented in by Ron Rivest, Adi Shamir, and Leonard Adleman), Digital Signature Algorithm (DSA) also known as asymmetric key generation and other data values used in digital signatures.
It is important for the security and effectiveness of the cryptographic algorithms that the random numbers used in cryptographic operations are of “good” quality, and are kept secret. Random numbers that are predictable open the cryptographic algorithms (or their keys) to attack. Equally, it is of little use to generate a secret key (for a symmetric or an asymmetric algorithm) if the random numbers used for the key are leaked to the outside world.
The act of testing the random numbers for “goodness” or entropy on some embedded systems, such as smart cards, can leak the value of the random bits to the outside world via side channels. Currently, standards for pseudorandom number generators do not solve this problem. Furthermore, embedded devices are susceptible to problems in repeatedly writing to persistent memory, such as Electrically Erasable Programmable Read Only Memory (EEPROM) or Flash memory, that are called “HotSpots”. Such memories can be written only a limited number of times, and if that limit is exceeded, then data can no longer be written reliably to the same location.
Current implementations use a stored seed in EEPROM to initialize the RNG and continuously update the seed, thus creating a HotSpot.
There are two fundamental types of Random Number Generators (RNG), namely hardware or “True” Random Number Generators (TRNG), and software or Pseudo Random Number generator (PRNG) that are utilized in cryptographic operations.
A TRNG is produced by a number of ways through electronic circuits. High quality circuits use, for example, a method of using two noise diodes and amplifying the output on to a frequency carrier envelope or by a Voltage Controlled Oscillator (VCO). The output becomes Transistor-transistor logic (TTL) or Complementary Metal Oxide Semiconductor (CMOS) logic that can be correlated to zeros and ones.
As a True RNG may still include bias and correlation from the output random bit stream, it must be tested through software to ensure that there are non-predictable patterns. Currently, there are no standards for non-deterministic testing of TRNG, so they must use what is called continuous output testing (sampling the output).
The Application Notes and Interpretation of the Scheme (AIS) from Bundesamt für Sicherheit in der Informationstechnik (BSI), a German Certification body is the standard owner for AIS 31 and AIS 20. The AIS 31 standard discusses this type of testing (i.e., sampling the output), but for embedded devices where startup performance is critical, this becomes unacceptably slow.
If a TRNG is not supported in an embedded device, then an implementation of a PRNG is usually incorporated. A PRNG is an algorithm that generates a sequence of zeros and ones. The quality of output can be seeded from a number of sources like clock frequency, date/time and other inputs. Cryptography can be used to manipulate the seed like Message-Digest Algorithms (MD5) or Secure Hash Standard (SHA1). These manipulators are called message digests, which act like a fingerprint for data. These techniques decrease the probability that repeatable patterns will occur. There are a number of statistical tests that can be run against the random bit output, that are described in Federal Information Processing Standard (FIPS) 140-1, but in FIPS 140-2, these tests have been dropped. FIPS 140-2 recommends a continuous output testing instead.
The basic software pseudo random number generator (PRNG) has two inputs and an output according to FIPS 186-2.
Referring to FIG. 1, a PRNG 10 receives as input a seed 12 and an optional user input 14. PRNG 10 outputs a random bit stream 16. PRNG 10 is, on system start-up, initialized with secret seed 12, and optional user input 14. Then each time the PRNG 10 is called, it generates additional pseudo random bits 16. The algorithm used within the PRNG is defined in the DSA standard FIPS 186-2.
U.S. Pat. No. 6,628,786, entitled “Distributed state random number generator and method for utilizing same”, describes networked computers generating and sharing entropy in proportion to the need for random numbers utilized to initialize the internal state of random number generators residing on the computers.
In U.S. Pat. No. 6,480,072 entitled “Method and apparatus for generating random numbers”, a random number generator generates high quality random numbers by sampling the output of a Voltage Controlled Oscillator (VCO) at a frequency much lower than the frequency of the oscillator output. In U.S. Pat. No. 6,253,223 entitled “Robust random number generator”, the use of one TRNG and one PRNG is described to provide the mechanism to produce random bits. These three references are herein incorporated by reference in their entirety.
Each of the prior art references described above lack the security features to resist Side Channel Attacks (SCA). They also lack any reference to standards, the secure initial loading of the seed, and hot spot prevention. Therefore, the microcontroller's signals and/or their associated memory/data can be read by external scanning techniques. These techniques come under the class of Side Channel Attacks (SCA) and include power analysis, timing analysis, RF analysis, and template attacks, etc.
One example of an attack is a Power Analysis attack that measures the current consumed by a device, which correlates to the computation being performed within it. Power analysis can reveal the bit sequences that are being processed in the microcontroller, hence making the data known. Examples of well-known Power Analysis attacks include Simple Power Analysis (SPA), Differential Power Analysis (DPA) and template attacks. Related classes of attacks known as Electromagnetic Attacks involve capturing the electromagnetic (EM) emanations from the device. There are also known examples of attacks with combined information from multiple side-channels such as power and EM-emanations.
Another example of prior art problems includes a Trusted Computing Group (TCG) which includes a method within its secure bootstrap process to update its seed value for the RNG at the end of the devices active session. This seed update process can potentially be replayed when writing to non-volatile memory (NVM) by powering down the device before the seed is updated. This means that the same seed value is being used over and over again until the complete seed value can be obtained.